Cuando llamas a reversed() en una matriz en Swift, obtienes una ReverseCollection que simplemente envuelve la matriz original con acceso inverso. Por lo tanto, esto es extremadamente eficiente:
let arr = [1,2,3,4] for i in arr.reversed() { print(i) } En realidad, nada se revirtió, excepto el acceso; la complejidad temporal de reversed aquí es O(1). ¡Frio!
Pero cuando indexo en reversed() por un número entero y reviso la Ayuda rápida, parece que perdí toda esa eficiencia; Me muestran la Secuencia reversed() que genera una nueva matriz:
let arr = [1,2,3,4] let i = arr.reversed()[1] // ???? this is a different `reversed()`! Y esto parece ser cierto, porque una matriz reversed() no admite, en sí misma, la indexación por número:
let arr = [1,2,3,4] let rev = arr.reversed() let i = rev[1] // compile error! Entonces mi pregunta es: ¿es realmente cierto que la indexación por número en una matriz reversed() , como en mi segundo ejemplo, pierde la eficiencia de la inversión del índice ReverseCollection?
Sí, la indexación por Int está causando que pierda su acceso O(1) a la matriz invertida. ¡Bastante pillado!
Como nota, reversed() aquí es un método sobrecargado; en Array específicamente, tiene dos definiciones para elegir:
BidirectionalCollection.reversed() , que devuelve una ReversedCollection , ySequence.reversed() , que convierte cualquier secuencia en un [Element] invertido La sobrecarga aquí es más confusa para Array en sí, porque es el único tipo de Sequence tal que type(of: x) == type(of: x.reversed()) .
El verificador de tipos de Swift prefiere sobrecargas más específicas a las menos específicas, por lo que, en general, el compilador utilizará la sobrecarga de BidirectionalCollection en lugar de la de Sequence siempre que sea posible. El rub: BidirectionalCollection tiene un tipo de índice opaco y no se puede indexar usando un Int ; cuando indexa la colección con un Int , el compilador se ve obligado a elegir la sobrecarga de Sequence sobre la de BidirectionalCollection . Esta es también la razón por la que su segundo ejemplo de código no se compila: la inferencia de código Swift no tiene en cuenta el contexto circundante en otras líneas; por sí solo, se prefiere que rev sea un ReversedCollection<Array<Int>> , por lo que se produce un error al intentar indexarlo con un Int .
Puedes ver esto un poco más claramente con lo siguiente:
func collType1<T: Collection>(_: T) { print(T.self) // ReversedCollection<Array<Int>> print(T.Index.self) // Index } func collType2<T: Collection>(_: T) where T.Index == Int { print(T.self) // Array<Int> print(T.Index.self) // Int } let x: [Int] = [1, 2, 3] collType1(x.reversed()) collType2(x.reversed()) Para que no se pregunte si el compilador puede optimizar esto cuando el hecho de la indexación basada en Int parece no tener otros efectos secundarios, en el momento de escribir este artículo, la respuesta parece ser "no". La salida de Godbolt es demasiado larga para reproducirla aquí, pero por el momento, comparando
func foo1(_ array: [Int]) { if array.reversed()[100] > 42 { print("Wow!") } }con
func foo2(_ array: [Int]) { if array.reversed().dropFirst(100).first! > 42 { print("Wow!") } } con optimizaciones habilitadas muestra foo2 realizando acceso directo a la matriz
cmp qword ptr [rdi + 8*rax + 24], 43 habiendo optimizado el envoltorio ReversedCollection por completo, mientras que foo1 pasa por una indirección significativamente mayor.
Ferber explicó muy bien el motivo.
Aquí hay una solución ad-hoc (que puede no ser la preferida por todos, porque estamos ampliando los tipos de la biblioteca estándar):
// RandomAccessCollection ensures fast index creation extension ReversedCollection where Base: RandomAccessCollection { subscript(_ offset: Int) -> Element { let index = index(startIndex, offsetBy: offset) return self[index] } } [1, 2, 3].reversed()[0] // 3